﻿#include <iostream>
#include "../Matrix/Matrix.h"

static const int M[] = {
	1, 1, 0,
	0, 0, 1,
	1, 0, 0,
};

static int howManyCow(int years)
{
	switch (years)
	{
	case 1:
		return 1;

	case 2:
		return 2;

	case 3:
		return 3;

	case 4:
		return 4;

	case 5:
		return 6;

	case 6:
		return 9;

	case 7:
		return 13;
	}

	int f3_2_1[] = {
		howManyCow(3), howManyCow(2), howManyCow(1),
	};

	int* m = powMatrix(M, 3, 3, years - 3);
	int* resM = multiMatrix(f3_2_1, 1, 3, m, 3, 3);
	int res = resM[0];
	free(resM);
	free(m);
	return res;
}

//  农场养母牛，一头母牛3年之后可以再生小母牛，小母牛3年之后长大了可以再生小母牛...
//  问，N年之后，一共有多少头牛 ?
// 
// 第一年，农场引进了一头母牛A；
//  第二年，A生下了B；
//  第三年，A生下了C；
//  第四年，A生下了D；
//  第五年，A生下了E，B生下了F
//  第六年，A生下了G，B生下了H，C生下了I
//  ...
// 
// 则有如下规律:
// 年数 : 1   2   3   4   5   6   7...
//  牛数 : 1   2   3   4   6   9  13...
// 
// F(1) = 1
//  F(2) = 2
//  F(3) = 3
//  F(4) = 4
//  F(5) = 6
//  F(6) = 9
//  F(7) = 13
//  ...
// 
// 于是有F(N) = F(N - 1) + F(N - 3)
// 
// 
//                                                                 a, b, c
//  [F(N), F(N - 1), F(N - 2)] = [F(N - 1), F(N - 2), F(N - 3)] * [d, e, f]
//                                                                 g, h, i
// 
// 于是：
// 
//                                             a, b, c
//  [F(4), F(3), F(2)] = [F(3), F(2), F(1)] * [d, e, f]
//                                             g, h, i
// 
//                                             a, b, c
//  [F(5), F(4), F(3)] = [F(4), F(3), F(2)] * [d, e, f]
//                                             g, h, i
// 
//                                             a, b, c
//  [F(6), F(5), F(4)] = [F(5), F(4), F(3)] * [d, e, f]
//                                             g, h, i
// 
//  a = 1
//  b = 1
//  c = 0
//  d = 0
//  e = 0
//  f = 1
//  g = 1
//  h = 0
//  i = 0
// 
// 
//                                                     a, b, c
//  [F(N), F(N - 1), F(N - 2)] = [F(3), F(2), F(1)] * [d, e, f] ^ (N - 3)
//                                                     g, h, i
int main_Cow()
{
	for (int years = 1; years <= 50; years++)
	{
		printf("Cow[%d]=%d\n", years, howManyCow(years));
	}

	return 0;
}